Search for: All records

Abstract We introduce partitioned matching games as a suitable model for international kidney exchange programmes, where in each round the total number of available kidney transplants needs to be distributed amongst the participating countries in a “fair” way. A partitioned matching game (N, v) is defined on a graph$$G=(V,E)$$ $G=(V,E)$with an edge weightingwand a partition$$V=V_1 \cup \dots \cup V_n$$ $V=V_1\cup \cdots \cup V_n$. The player set is$$N = \{ 1, \dots , n\}$$ $N=\{1,\cdots ,n\}$, and player$$p \in N$$ $p\in N$owns the vertices in$$V_p$$ $V_p$. The valuev(S) of a coalition $$S \subseteq N$$ $S\subseteq N$is the maximum weight of a matching in the subgraph ofGinduced by the vertices owned by the players in S. If$$|V_p|=1$$ $|V_p|=1$for all$$p\in N$$ $p\in N$, then we obtain the classical matching game. Let$$c=\max \{|V_p| \; |\; 1\le p\le n\}$$ $c=max\left\{\right|V_p\left|\right|1\le p\le n\}$be the width of (N, v). We prove that checking core non-emptiness is polynomial-time solvable if$$c\le 2$$ $c\le 2$but co--hard if$$c\le 3$$ $c\le 3$. We do this via pinpointing a relationship with the known class ofb-matching games and completing the complexity classification on testing core non-emptiness forb-matching games. With respect to our application, we prove a number of complexity results on choosing, out of possibly many optimal solutions, one that leads to a kidney transplant distribution that is as close as possible to some prescribed fair distribution. 

We study housing markets as introduced by Shapley and Scarf. We investigate the computational complexity of various questions regarding the situation of an agent a in a housing market H: we show that it is [Formula: see text]-hard to find an allocation in the core of H in which (i) a receives a certain house, (ii) a does not receive a certain house, or (iii) a receives a house other than a’s own. We prove that the core of housing markets respects improvement in the following sense: given an allocation in the core of H in which agent a receives a house h, if the value of the house owned by a increases, then the resulting housing market admits an allocation in its core in which a receives either h or a house that a prefers to h; moreover, such an allocation can be found efficiently. We further show an analogous result in the Stable Roommates setting by proving that stable matchings in a one-sided market also respect improvement. Funding: This work was supported by the Hungarian Scientific Research Fund [Grants K124171, K128611]. I. Schlotter is supported by the Hungarian Academy of Sciences under its Momentum Programme (LP2021-2) and its János Bolyai Research Scholarship. The research reported in this paper and carried out by T. Fleiner at the Budapest University of Technology and Economics was supported by the “TKP2020, National Challenges Program” of the National Research Development and Innovation Office [BME NC TKP2020 and OTKA K143858] and by the Higher Education Excellence Program of the Ministry of Human Capacities in the frame of the Artificial Intelligence research area of the Budapest University of Technology and Economics (BME FIKP-MI/SC). P. Biró gratefully acknowledges financial support from the Hungarian Scientific Research Fund, OTKA [Grant K143858] and the Hungarian Academy of Sciences [Momentum Grant LP2021-2].